package problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class SolutionNonRecursive {
	public class TreeNode {
	      public int val;
	      public TreeNode left;
	      public TreeNode right;
	      public TreeNode(int x) { val = x; }
	      
	      public String toString(){
	    	  return "["+val+":left:"+(left==null?"null":left.toString())+",right:"+(right==null?"null":right.toString())+"]";
	      }
	 }
	
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder == null || preorder.length ==0){
            return null;
        }
		Map<Integer,Integer> inorderMap=new HashMap<>();
		for(int i=0;i<inorder.length;i++){
			inorderMap.put(inorder[i], i);
		}
		Stack<TreeNode> stack=new Stack<>();
		TreeNode root=new TreeNode(preorder[0]);
		stack.push(root);
		for(int i=1;i<preorder.length;i++){
			TreeNode top=stack.peek();
			TreeNode cur=new TreeNode(preorder[i]);
			int inorderIndex=inorderMap.get(preorder[i]);
			int topIndex=inorderMap.get(top.val);
			if(inorderIndex<topIndex){
				top.left=cur;
			}else{
				while(topIndex<inorderIndex){
					top=stack.pop();
					topIndex=stack.isEmpty()?Integer.MAX_VALUE:inorderMap.get(stack.peek().val);
				}
				top.right=cur;
			}
			stack.push(cur);
		}
		return root;
	}
}
